In developing operations strategy, facility location is of prime importance. Location of facility has impact on many things such as cost and time of delievery of goods. While establishing capacity of the factory, deciding customers to serve from a particular facility, we have to build a model that optimizes the profit or reduces the cost of operations. It has applications in disaster management also. For example, during pandemic, it was important to reduce the overall cost of vaccination. With help of the model discuss here, one can find the optimum facilities location while minimizing the overall cost of the operations. Genetic algorithm has been used as an optimizer in this case. In this case, each customer has been categoried into centroid or zones using unsupervised clustering.
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import math
import random
#set parameters
num_customer = 10000
Max_facilities = 8
candidates_fac = 20
num_gaussian = 10
threshold =0.99
clusters = np.random.multinomial(num_customer, [1/num_gaussian]*num_gaussian)
customers = []
for i in range(num_gaussian):
centers = (random.random()*0.1+28.5, random.random()*0.1+77)
customers += [(random.gauss(0,0.01)+centers[0], random.gauss(0,0.01)+centers[1]) for j in range(clusters[i])]
cust = pd.DataFrame(customers)
cust.columns = ['Lat', 'Lon']
import plotly.graph_objects as G
from sklearn.cluster import MiniBatchKMeans
lat_center = np.mean(cust['Lat'])
long_center = np.mean(cust['Lon'])
num_clusters = 10
seed = 1000
kmeans = MiniBatchKMeans(n_clusters=num_clusters, init_size=3*num_clusters,
random_state=seed).fit(customers)
memberships = list(kmeans.labels_)
centroids = list(kmeans.cluster_centers_) # Center point for each cluster
weights = list(np.histogram(memberships, bins=num_clusters)[0]) # Number of customers in each cluster
print('First cluster center:', centroids[0])
print('Weights for first 10 clusters:', weights[:10])
centro = pd.DataFrame(centroids, columns=['Lat','Lon'])
centro['Demand'] = weights
fac_loc = [(random.random()*0.09+28.5, random.random()*0.08+77) for x in range(candidates_fac)]
#fac_loc = pd.read_csv('fac_loc.csv')
faclities = pd.DataFrame(fac_loc, columns=['Lat','Lon'])
faclities['Capacity'] = np.ones(len(faclities))*1000
fig = G.Figure(G.Scattermapbox(
name='customers',
mode='markers',
lon = cust['Lon'],
lat= cust['Lat'],
marker = {'size': 3},
line = dict(width = 4.5, color = 'pink')))
fig.add_traces(G.Scattermapbox(
name='centroids',
mode='markers',
lon = centro['Lon'],
lat= centro['Lat'],
marker = {'size': 5},
line = dict(width = 4.5, color = 'green')))
fig.add_traces(G.Scattermapbox(
name='Candidate Facilities',
mode='markers',
lon = faclities['Lon'],
lat= faclities['Lat'],
marker = {'size': 10},
line = dict(width = 4.5, color = 'blue')))
lat_center = np.mean(cust['Lat'])
long_center = np.mean(cust['Lon'])
fig.update_layout(mapbox_style = 'stamen-terrain', mapbox_center_lat = lat_center, mapbox_center_lon = long_center)
fig.update_layout(margin={"r":0,"l":0,"t":0,"b":0}, mapbox = {'center':{'lat':lat_center,'lon':long_center},'zoom':11})
fig.show()
def distance(p1,p2):
Lo1 = p1[1]
La1 = p1[0]
Lo2 = p2[1]
La2 = p2[0]
Lo1 = math.radians(Lo1)
Lo2 = math.radians(Lo2)
La1 = math.radians(La1)
La2 = math.radians(La2)
# Using the "Haversine formula"
D_Lo = Lo2 - Lo1
D_La = La2 - La1
P = math.sin(D_La / 2)**2 + math.cos(La1) * math.cos(La2) * math.sin(D_Lo / 2)**2
Q = 2 * math.asin(math.sqrt(P))
# The radius of earth in kilometres.
R_km = 6371
# Then, we will calculate the result
return(Q * R_km)
def dist_mat(centroids, facilities):
dmat = []
for i in range(len(centroids)):
for j in range(len(facilities)):
dmat.append(['centroid:'+str(i), 'facility:'+str(j), distance(centroids[i], facilities[j])])
dfm = pd.DataFrame(dmat, columns=['Centroid','facility','distance'])
return dfm
distf = dist_mat(centroids, fac_loc)
pop_size =100
cross_rate = 0.9
mut_rate = 1/50
iterations = 500
import hemi_GA6 as hga
error = []
best, best_value = hga.GA_function(hga.fitness, iterations, pop_size, cross_rate,
mut_rate, centroids, distf, error,Max_facilities)
plt.plot(error)
faclities['assign'] = np.array(best[1])
selected_fac = faclities[faclities['assign']==1]
selected_fac
vv = best[0]
aaa=np.where(np.array(vv[9])==1)
arr = np.array([11,12,13,14])
selected_fac.iloc[7,0]
qq = [selected_fac.iloc[[np.where(np.array(vv[i])==1)[0][0]]] for i in range(len(centro))]
aa = []
bb = []
for i in range(len(centro)):
xx = np.where(np.array(vv[i])==1)[0][0]
print(xx)
aa.append(selected_fac.iloc[xx,0])
bb.append(selected_fac.iloc[xx,1])
centro['fac_lat'] = np.array(aa)
centro['fac_lon'] = np.array(bb)
centro.to_csv('result.csv')
Selected facilities has been shown in below plot (with red dot) along with the assigned centroid of customers with connected lines
fig = G.Figure(G.Scattermapbox(
name='customers',
mode='markers',
lon = cust['Lon'],
lat= cust['Lat'],
marker = {'size': 3},
line = dict(width = 4.5, color = 'pink')))
fig.add_traces(G.Scattermapbox(
name='centroids',
mode='markers',
lon = centro['Lon'],
lat= centro['Lat'],
marker = {'size': 5},
line = dict(width = 4.5, color = 'green')))
fig.add_traces(G.Scattermapbox(
name='Candidate Facilities',
mode='markers',
lon = faclities['Lon'],
lat= faclities['Lat'],
marker = {'size': 10},
line = dict(width = 4.5, color = 'blue')))
fig.add_traces(G.Scattermapbox(
name='Selected Facilities',
mode='markers',
lon = centro['fac_lon'],
lat= centro['fac_lat'],
marker = {'size': 10},
line = dict(width = 4.5, color = 'red')))
for i in range(len(centro)):
fig.add_traces(G.Scattermapbox(
name='assigned Facilities',
mode='lines',
lon = [centro.iloc[i,1], centro.iloc[i,4]],
lat= [centro.iloc[i,0], centro.iloc[i,3]],
line = dict(width = 1, color = 'black')))
lat_center = np.mean(cust['Lat'])
long_center = np.mean(cust['Lon'])
fig.update_layout(mapbox_style = 'stamen-terrain', mapbox_center_lat = lat_center, mapbox_center_lon = long_center)
fig.update_layout(margin={"r":0,"l":0,"t":0,"b":0}, mapbox = {'center':{'lat':lat_center,'lon':long_center},'zoom':11})
fig.show()